LeetCode 236、二叉树的最近公共祖先

一、题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的最近公共祖先（ LeetCode 236 ）:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        // 1、如果此时访问的节点 root 为 null，那么直接返回 null
        if(root == null ) return null;

        // 2、如果此时访问的节点 root 为指定节点 p，那么返回 p 这个节点
        if(root == p)  return p;

        // 3、如果此时访问的节点 root 为指定节点 q，那么返回 q 这个节点
        if(root == q) return q;
        
        // 4、经过上面 1、2、3 的判断之后，root 这个节点必然不是 p、q、null 这三种情况的节点
        // 接下来，去递归的判断当前节点 root 的左右子树是否包含 p 、q 这两个指定节点


        // 5、递归的去查找 root 的左子树，判断是否包含p 、q 这两个指定节点
        // 如果 root 的左子树节点和它的左子树所有节点中包含 p，那么 left 的值就是 p
        // 如果 root 的左子树节点和它的左子树所有节点中包含 q，那么 left 的值就是 q
        // 如果 root 的左子树节点和它的左子树所有节点中既不包含 p，也不包含 q，那么 left 的值就是 null
        TreeNode left = lowestCommonAncestor(root.left, p, q);


        // 6、递归的去查找 root 的右子树，判断是否包含p 、q 这两个指定节点
        // 如果 root 的右子树节点和它的右子树所有节点中包含 p，那么 right 的值就是 p
        // 如果 root 的右子树节点和它的右子树所有节点中包含 q，那么 right 的值就是 q
        // 如果 root 的右子树节点和它的右子树所有节点中既不包含 p，也不包含 q，那么 right 的值就是 null
        TreeNode right = lowestCommonAncestor(root.right, p, q);


        // 7、判断完当前节点 root 、 root 的左子树 left、root 的右子树 right 的情况后
        // 开始向父节点传递信息

        // 8、如果 root 节点的左子树 left 和右子树 right 都没有找到指定节点 p、q
        // 并且 root 自己本身也不是指定节点 p、q
        // 那么它给父节点传递的信息就是以 root 为根节点的那颗二叉树没有指定节点 p、q 
        if(left == null && right == null){

            // 返回 null，告诉 root 的父节点，这里没找到指定节点 p、q
            return null;

        // 9、如果在 root 节点的左子树 left 中没有找到指定节点 p、q 
        // 那么以 root 为根节点的那颗二叉树能不能找到指定节点 p、q  完全取决于 right 了
        }else if(left == null){

            // 返回 right ，告诉 root 的父节点，能不能找到指定节点 p、q  完全取决于 right 
            return right;

        // 10、如果在 root 节点的右子树 right 中没有找到指定节点 p、q 
        // 那么以 root 为根节点的那颗二叉树能不能找到指定节点 p、q  完全取决于 left 了
        }else if(right == null){

            // 返回 left ，告诉 root 的父节点，能不能找到指定节点 p、q  完全取决于 left 
            return left;

        // 11、此时，left != null 并且 right != null
        // 这说明在以 root 节点为根节点的那棵二叉树中找到了指定节点 p ，也找到了指定节点 q 
        // 那么就告诉父节点，root 就是 p、q 的最近公共祖先
        }else{

            // 返回 root ，告诉 root 的父节点，root 就是 p、q 的最近公共祖先
            return root;
        } 
    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 二叉树的最近公共祖先（ LeetCode 236 ）:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        // 1、如果此时访问的节点 root 为 NULL，那么直接返回 NULL
        if(root == NULL ) return NULL;

        // 2、如果此时访问的节点 root 为指定节点 p，那么返回 p 这个节点
        if(root == p)  return p;

        // 3、如果此时访问的节点 root 为指定节点 q，那么返回 q 这个节点
        if(root == q) return q;

        // 4、经过上面 1、2、3 的判断之后，root 这个节点必然不是 p、q、NULL 这三种情况的节点
        // 接下来，去递归的判断当前节点 root 的左右子树是否包含 p 、q 这两个指定节点


        // 5、递归的去查找 root 的左子树，判断是否包含p 、q 这两个指定节点
        // 如果 root 的左子树节点和它的左子树所有节点中包含 p，那么 left 的值就是 p
        // 如果 root 的左子树节点和它的左子树所有节点中包含 q，那么 left 的值就是 q
        // 如果 root 的左子树节点和它的左子树所有节点中既不包含 p，也不包含 q，那么 left 的值就是 NULL
        TreeNode* left = lowestCommonAncestor(root->left, p, q);


        // 6、递归的去查找 root 的右子树，判断是否包含p 、q 这两个指定节点
        // 如果 root 的右子树节点和它的右子树所有节点中包含 p，那么 right 的值就是 p
        // 如果 root 的右子树节点和它的右子树所有节点中包含 q，那么 right 的值就是 q
        // 如果 root 的右子树节点和它的右子树所有节点中既不包含 p，也不包含 q，那么 right 的值就是 NULL
        TreeNode* right = lowestCommonAncestor(root->right, p, q);


        // 7、判断完当前节点 root 、 root 的左子树 left、root 的右子树 right 的情况后
        // 开始向父节点传递信息

        // 8、如果 root 节点的左子树 left 和右子树 right 都没有找到指定节点 p、q
        // 并且 root 自己本身也不是指定节点 p、q
        // 那么它给父节点传递的信息就是以 root 为根节点的那颗二叉树没有指定节点 p、q 
        if(left == NULL && right == NULL){

            // 返回 NULL，告诉 root 的父节点，这里没找到指定节点 p、q
            return NULL;

        // 9、如果在 root 节点的左子树 left 中没有找到指定节点 p、q 
        // 那么以 root 为根节点的那颗二叉树能不能找到指定节点 p、q  完全取决于 right 了
        }else if(left == NULL){

            // 返回 right ，告诉 root 的父节点，能不能找到指定节点 p、q  完全取决于 right 
            return right;

        // 10、如果在 root 节点的右子树 right 中没有找到指定节点 p、q 
        // 那么以 root 为根节点的那颗二叉树能不能找到指定节点 p、q  完全取决于 left 了
        }else if(right == NULL){

            // 返回 left ，告诉 root 的父节点，能不能找到指定节点 p、q  完全取决于 left 
            return left;

        // 11、此时，left != NULL 并且 right != NULL
        // 这说明在以 root 节点为根节点的那棵二叉树中找到了指定节点 p ，也找到了指定节点 q 
        // 那么就告诉父节点，root 就是 p、q 的最近公共祖先
        }else{

            // 返回 root ，告诉 root 的父节点，root 就是 p、q 的最近公共祖先
            return root;
        } 
    }
};

3、Python 代码

登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 二叉树的最近公共祖先（ LeetCode 236 ）:https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode' ) -> 'TreeNode':

        # 1、如果此时访问的节点 root 为 null，那么直接返回 null
        if not root:  
           return None

        # 2、如果此时访问的节点 root 为指定节点 p，那么返回 p 这个节点
        if root == p : return p

        # 3、如果此时访问的节点 root 为指定节点 q，那么返回 q 这个节点
        if root == q : return q
        
        # 4、经过上面 1、2、3 的判断之后，root 这个节点必然不是 p、q、null 这三种情况的节点
        # 接下来，去递归的判断当前节点 root 的左右子树是否包含 p 、q 这两个指定节点


        # 5、递归的去查找 root 的左子树，判断是否包含p 、q 这两个指定节点
        # 如果 root 的左子树节点和它的左子树所有节点中包含 p，那么 left 的值就是 p
        # 如果 root 的左子树节点和它的左子树所有节点中包含 q，那么 left 的值就是 q
        # 如果 root 的左子树节点和它的左子树所有节点中既不包含 p，也不包含 q，那么 left 的值就是 null
        left = self.lowestCommonAncestor(root.left,p,q)


        # 6、递归的去查找 root 的右子树，判断是否包含p 、q 这两个指定节点
        # 如果 root 的右子树节点和它的右子树所有节点中包含 p，那么 right 的值就是 p
        # 如果 root 的右子树节点和它的右子树所有节点中包含 q，那么 right 的值就是 q
        # 如果 root 的右子树节点和它的右子树所有节点中既不包含 p，也不包含 q，那么 right 的值就是 null
        right = self.lowestCommonAncestor(root.right,p,q)


        # 7、判断完当前节点 root 、 root 的左子树 left、root 的右子树 right 的情况后
        # 开始向父节点传递信息

        # 8、如果 root 节点的左子树 left 和右子树 right 都没有找到指定节点 p、q
        # 并且 root 自己本身也不是指定节点 p、q
        # 那么它给父节点传递的信息就是以 root 为根节点的那颗二叉树没有指定节点 p、q 
        if not left and not right :

            # 返回 null，告诉 root 的父节点，这里没找到指定节点 p、q
            return None

        # 9、如果在 root 节点的左子树 left 中没有找到指定节点 p、q 
        # 那么以 root 为根节点的那颗二叉树能不能找到指定节点 p、q  完全取决于 right 了
        elif not left :

            # 返回 right ，告诉 root 的父节点，能不能找到指定节点 p、q  完全取决于 right 
            return right

        # 10、如果在 root 节点的右子树 right 中没有找到指定节点 p、q 
        # 那么以 root 为根节点的那颗二叉树能不能找到指定节点 p、q  完全取决于 left 了
        elif not right :

            # 返回 left ，告诉 root 的父节点，能不能找到指定节点 p、q  完全取决于 left 
            return left

        # 11、此时，left != null 并且 right != null
        # 这说明在以 root 节点为根节点的那棵二叉树中找到了指定节点 p ，也找到了指定节点 q 
        # 那么就告诉父节点，root 就是 p、q 的最近公共祖先
        else:
            
            # 返回 root ，告诉 root 的父节点，root 就是 p、q 的最近公共祖先
            return root